#include<iostream>
#include<stack>
#include<string>
#include<sstream>
#include<stdlib.h>
using namespace std;

extern int cnt1 = 0, cnt2 = 0;//记录括号个数
extern int cnt3 = 0, cnt4 = 0;//记录操作数和操作符个数

//设置符号优先级
int Priority(char ch)
{
	switch (ch)
	{
	case '+' :
	case '-' :
		return 1;
		break;
	case '*':
	case '/':
		return 2;
		break;
	case '(':
	case ')':
		return 0;
		break;
	default: 
		return -1;
		break;
	}
}

//判断是否为括号
int brackets(char ch)
{
	if (ch == '(' || ch == ')')
		return 1;
	else return 0;
}

//判断符号优先级
void check(char ch, stack<char>& m_operator, string& suffix)
{
	if (m_operator.empty()) {
		m_operator.push(ch);
		return;
	}
	if (brackets(ch)) {
		if (ch == '(') {
			m_operator.push(ch);
			cnt1++;
		}
		else {
			//弹出所有元素直到遇到左括号
			while (m_operator.top() != '(') {
				suffix += m_operator.top();
				m_operator.pop();
			}
			cnt2++;
			m_operator.pop();//删除左括号
		}
	}
	else {
		if (Priority(ch) > Priority(m_operator.top())) {
			m_operator.push(ch);
		}
		else {
			suffix += m_operator.top();
			m_operator.pop();

			check(ch, m_operator, suffix);

		}

	}
	
}
//中缀表达式转换为后缀表达式
string Transfer(string& infix) {
	stack<char> m_operator;
	string suffix;

	for (int i = 0; i < infix.size(); i++) {
		if (infix[i] >= '0' && infix[i] <= '9') {
			suffix += infix[i];
			cnt3++;
		}
		else if (Priority(infix[i]) >= 0) {
			check(infix[i], m_operator, suffix);
			cnt4++;
		}
		else continue;//去掉非操作数和操作符
	}
	cnt4 = cnt4 - cnt2 - cnt1;
	//如果左括号数小于右括号数，或者操作数和操作符号相差不为1，输入有误，结束
	if (cnt1 != cnt2|| cnt3 != cnt4 + 1) {
		cout << "输入有误请重新输入！" << endl;
		exit(-1);
	}

	while (!m_operator.empty()) {
		suffix += m_operator.top();
		m_operator.pop();
	}

	return suffix;
}

//计算后缀表达式
int cal(const string suffix)
{
	stack<int> mystack;
	int first, last,result=0;
	for (int i = 0; i < suffix.size(); i++) {
		if (suffix[i] >= '0' && suffix[i] <= '9') {
			mystack.push(suffix[i] - '0');
		}
		else if (Priority(suffix[i]) >= 0) {
			last =(int)mystack.top();
			mystack.pop();
			first = (int)mystack.top();
			mystack.pop();
			if (suffix[i] == '+') {
				result = first + last;
				mystack.push(result);
			}
			if (suffix[i] == '-') {
				result = first - last;
				mystack.push(result);
			}if (suffix[i] == '*') {
				result = first * last;
				mystack.push(result);
			}if (suffix[i] == '/') {
				if (last == 0) {
					cout << "输入有误，除数不能为零，请重新输入！" << endl;
					exit(-1);
				}
				result = first / last;
				mystack.push(result);
			}
		}
	}
	result = (int)mystack.top();
	mystack.pop();
	return result;
	
}

int main() {
	string infix,suffix;

	cout << "请输入要处理的字符串：" << endl;

	getline(cin, infix);
	suffix = Transfer(infix);
	cout << "转换为后缀表达式：" << endl;
	cout<<suffix<<endl;
	cout << "计算结果为：" << endl;
	cout << cal(suffix) << endl;
	return 0;
}
